# -*- coding: utf-8 -*-
"""
Created on Wed Aug 28 13:07:07 2019

@author: Administrator
"""

class ALNode:
    """邻接表节点
    """
    def __init__(self, number, next_node):
        self.number = number
        self.next_node = next_node
        
class ALHead:
    """邻接表头结点
    """
    def __init__(self, number, tail, next_node):
        self.number = number
        self.tail = tail
        self.next_node = next_node


class GraphAL:
    """基于邻接表的图数据类型
    """
    def __init__(self, mat = []):
        """参数mat：邻接矩阵
        """
        self._mat = []
        self._vnum = 0
        
        # 遍历时使用
        self.visited = []
        self.queue = []

        # 验证是否为方阵
        self.is_valid()
       
        # 如果是方阵，复制mat到内部_mat
        rows = len(mat)
        for i in range(rows):
            # 添加节点
            vertex = ALHead(i, None, None)
            self._mat.append(vertex)
            
            cols = len(rows[i])
            for j in range(cols):
                # 排除非0元素（即节点没有连接）
                if mat[i][j] == 0:
                    continue
                
                # 创建新节点
                node = ALNode(j, None)
                
                # 如果是邻接表的第一个节点
                if self._mat[i].next_node == None:
                    self._mat[i].next_node = node
                    self._mat[i].tail = node
                else:
                    # 在邻接表尾节点后添加新节点
                    self._mat[i].tail.next_node = node
                    self._mat[i].tail = node
                
            # 更新图节点数量信息
            self._vnum = self._vnum + 1
    
    def is_valid(self):
        # 检查mat是否为方阵
        row = len(self._mat)
        for i in range(row):
            if len(self._mat[i]) != row:
                raise ValueError("mat 结构不符合！")
    
    def is_empty(self):
        if self._vnum == 0:
            return True
        return False
        
    def vertex_number(self):
        """获取图中所有节点
        """
        if self.is_empty():
            return 0
        else:
            return self._vnum
    
    def get_vertex(self, num):
        """获取第num个节点
        """
        if num < 0 or num >= self._vnum:
            return
        
        return self._mat[num]
    
    def get_mat(self):
        return self._mat
    
    def print_mat(self):
        """打印图类邻接表结构
        """
        for i in range(len(self._mat)):
            
            label = ""
            
            print("%d:" % self._mat[i].data)
            q = self._mat[i].next_node
            while q != None:
                label += "->%d" % q.data
                q = q.next_node
            
            print(label)
    
    def breath_first_search(self, v):
        """广度优先遍历
        参数：v 遍历起点
        返回值：result 遍历后的节点数据
        """
        result = []

        if self.is_empty():
            return result
        
        self.queue.append(v)
        
        # 遍历queue中每一个节点
        while self.queue:
            # 弹出首节点
            vertex = self.queue.pop(0)
            # 访问i节点    
            result.append(vertex.number)
            # i节点已被访问
            self.visited.append(vertex)
            
            # 依次访问与i节点连接的所有节点
            connected_vertex = self.get_connected_vertex(vertex)
            con_num = len(connected_vertex)
            
            # 连接节点加入queue
            for j in range(con_num):
                # 如果连接节点没有被访问 并且在队列里没有，则加入队列
                if self.not_visited(connected_vertex[j]) and self.not_queue(connected_vertex[j]):
                    self.queue.append(connected_vertex[j])
            
            # 访问完毕后，在访问下一层所有未访问过的节点
            
        return result
    
    def get_connected_vertex(self, vertex):
        """获取vertex的相连节点
        参数：vertex 某节点
        返回值：result 相连节点的list
        """
        result = []
        q = vertex.next_node
        while q != None:
            result.append(q)
            q = q.next_node
        return result
    
    
    def not_visited(self, vertex):
        num = len(self.visited)
        
        for i in range(num):
            if self.visited[i] == vertex:
                return False
        return True
    
    def not_queue(self, vertex):
        num = len(self.queue)
        
        for i in range(num):
            if self.queue[i] == vertex:
                return False
        return True

# 无权图的邻接矩阵
#mat = [[0,1,1],[1,0,1],[1,1,0]]
mat = [[0,1,1,1],[1,0,1,0],[1,1,0,0],[1,0,0,0]]
graph = GraphAL(mat)
#print(graph.vertex_number())

# 测试get_connected_vertex
#vertex2 = graph.get_vertex(2)
#result = graph.get_connected_vertex(vertex2)
#
#for i in range(len(result)):
#    print(result[i].data)

# 测试not_visited
#vertex0 = graph.get_vertex(0)
#print(graph.not_visited(vertex0))

# 打印图的邻接数组
#graph.print_mat()

#vertex0 = graph.get_vertex(0)
#result = graph.breath_first_search(vertex0)
#print(result)


